{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Tarjan算法\n",
    "\n",
    "**Tarjan算法** 是一种经典的基于深度优先搜索（DFS）的图算法，旨在高效地解决以下两类图论问题：\n",
    "\n",
    "-   **有向图：**Tarjan 算法可以找到所有**强连通分量**。\n",
    "-   **无向图：**Tarjan 算法可以找到所有的**割点**和**桥**。\n",
    "\n",
    "> **强连通分量（Strongly Connected Components, SCCs）**：一个强连通分量是一个子图，其中每两个顶点互相可达。\n",
    "> \n",
    "> **桥（Bridges）:** 指的是在图中删除后会增加图的连通分量的边，也就是删除该边就可以将原图分割为两个图的边。"
   ],
   "id": "f57ec1d6ef6481d7"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 在有向图中寻找强连通分量\n",
    "它基于深度优先搜索，并通过对每个节点记录两个重要值：\n",
    "\n",
    "-   **DFS 序号（disc）**：表示节点被访问的顺序。\n",
    "-   **Low 值（low）**：表示节点能够通过后向边（或者子树中的边）访问到的最早祖先节点的 DFS 序号。\n",
    "\n",
    "![image](./assets/img.png)\n",
    "\n",
    "在上图中，我们首先对原图进行深度遍历，在遍历中我们标记节点的属性（disc，low）。\n",
    "在深度遍历到节点 $e$ 时，到达终点，所以深度搜索将回溯到节点 $d$，此时发现，由于节点 $d$ 可以访问到的最早节点祖先为节点 $b$，所以下面将更新节点的属性 low=2。\n",
    "同理，此后也将更新节点c的 low=2。\n",
    "\n",
    "![image-1](./assets/img_1.png)\n",
    "\n",
    "下面将对节点 $f$ 进行访问，依次更新节点 $f$ 和节点 $g$，由于节点 $g$ 可以回溯的最早祖先为节点 $a$，所以更新节点 $f$ 和节点 $g$ 的low=1。\n",
    "\n",
    "![image-2](./assets/img_2.png)\n",
    "\n",
    "最后，就**可以根据各个节点的low的值来划分不同的强联通分量。**\n",
    "\n",
    "![image-3](./assets/img_3.png)"
   ],
   "id": "1857f304d0f058ad"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:14.721803Z",
     "start_time": "2024-10-17T03:38:14.374709Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from collections import defaultdict\n",
    "import igraph as ig\n",
    "import matplotlib.pyplot as plt"
   ],
   "id": "d999045d1f6643ee",
   "outputs": [],
   "execution_count": 2
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:14.737767Z",
     "start_time": "2024-10-17T03:38:14.722818Z"
    }
   },
   "cell_type": "code",
   "source": [
    "class DirectedGraph:\n",
    "    \"\"\"定义一个有向图\n",
    "    有向图使用一个字典表示，字典中的元素是一个数组，每个元素都表示了一个节点，数组记录了所有该节点指向的其他节点。\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, vertices):\n",
    "        self.V = vertices\n",
    "        self.graph = defaultdict(list)\n",
    "        self.time = 0\n",
    "\n",
    "    def add_edge(self, u, v):\n",
    "        self.graph[u].append(v)\n",
    "\n",
    "    def _tarjan_scc(self, u, low, disc, stack, stack_member, result):\n",
    "        disc[u] = self.time\n",
    "        low[u] = self.time\n",
    "        self.time += 1\n",
    "        stack.append(u)\n",
    "        stack_member[u] = True\n",
    "\n",
    "        # 遍历邻接点\n",
    "        for v in self.graph[u]:\n",
    "            if disc[v] == -1:  # v未被访问\n",
    "                self._tarjan_scc(v, low, disc, stack, stack_member, result)\n",
    "                low[u] = min(low[u], low[v])\n",
    "            elif stack_member[v]:  # v在栈中\n",
    "                low[u] = min(low[u], disc[v])\n",
    "\n",
    "        # 如果 u 是 SCC 的根节点\n",
    "        if low[u] == disc[u]:\n",
    "            scc = []\n",
    "            while True:\n",
    "                w = stack.pop()\n",
    "                stack_member[w] = False\n",
    "                scc.append(w)\n",
    "                if w == u:\n",
    "                    break\n",
    "            result.append(scc)\n",
    "\n",
    "    def find_sccs(self):\n",
    "        disc = [-1] * self.V  # 记录每个节点的发现时间\n",
    "        low = [-1] * self.V  # 记录节点的 Low 值\n",
    "        stack_member = [False] * self.V\n",
    "        stack = []\n",
    "        result = []\n",
    "\n",
    "        for i in range(self.V):\n",
    "            if disc[i] == -1:\n",
    "                self._tarjan_scc(i, low, disc, stack, stack_member, result)\n",
    "\n",
    "        return result"
   ],
   "id": "fca7ee16b32006aa",
   "outputs": [],
   "execution_count": 3
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:14.752774Z",
     "start_time": "2024-10-17T03:38:14.738772Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 示例使用\n",
    "g = DirectedGraph(7)\n",
    "edges = [(0, 1), (0, 5), (1, 2), (2, 3), (2, 4), (3, 4), (3, 1), (5, 6), (6, 0)]\n",
    "for i, j in edges:\n",
    "    g.add_edge(i, j)\n",
    "\n",
    "print(\"强连通分量:\", g.find_sccs())"
   ],
   "id": "411bdaa350fd5ca9",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "强连通分量: [[4], [3, 2, 1], [6, 5, 0]]\n"
     ]
    }
   ],
   "execution_count": 4
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:14.895522Z",
     "start_time": "2024-10-17T03:38:14.754782Z"
    }
   },
   "cell_type": "code",
   "source": [
    "n_vertices = 7\n",
    "g = ig.Graph(n_vertices, edges, directed=True)\n",
    "\n",
    "id_list = list(range(0, 10))\n",
    "g.vs[\"id\"] = id_list\n",
    "g.vs['weight'] = list(range(1, 13))\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(5, 5))\n",
    "ig.plot(\n",
    "    g,\n",
    "    target=ax,\n",
    "    # layout=\"circle\",  # print nodes in a circular layout\n",
    "    vertex_size=0.6,\n",
    "    vertex_frame_width=4.0,\n",
    "    vertex_color=\"lightblue\",\n",
    "    vertex_frame_color=\"white\",\n",
    "    vertex_label=g.vs[\"id\"],\n",
    "    vertex_label_size=10.0,\n",
    "    edge_color=\"gray\",\n",
    "    edge_arrow_size=0.01,\n",
    "    margin=40\n",
    ")\n",
    "plt.show()"
   ],
   "id": "fe8c1d26fcf4a199",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Figure size 500x500 with 1 Axes>"
      ],
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHoAAAGVCAYAAAAxPOUHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAj60lEQVR4nO2deZAk1X3nv3nV2XV39VnTM909J8z0nIAN4jCy5NVuIGvFSmvMro28BGYDyQpJa60EOlYoJCRLAVjH2lohLLNIWLe8sjACBYrAEjCMhhmGmYGGmR66Z/qsK+s+8to/ikpV31lVmVmVxyeCiJqi8qj+1Hv5jt97P0KSJAk2pofs9A3Y6IMt2iLYoi2CLdoi2KItgi3aItiiLYIt2iLYoi2CLdoi2KItgi3aItiiLYIt2iLYoi2CLdoi2KItgi3aItiiLYIt2iLYoi2CLdoi2KItgi3aItiiLYIt2iLYoi2CLdoi2KItAt3pGzA6mQqHdJkDW+ZQ4gSIACiCgM9BIehyIOxm4KapTt8mCHvZbPNwgoiZbAlTbBG5Kr/p5/u9TowFPRjwOkEQhA53uBpdRbNlDvFiBWyFR7bCgRclEACcNImgk0HQxaDf64SrC0rAeszmSji5mEVFEJs+NuxicHgwCJ9D/4pUc9GiJNV+/eki2Aq36edJAhjqcWF7yIuw26HlrTUFL0p4cYHFpVy5rfOQBLAv6sd4yKvSnSlDU9FsmcPxBRaZyubV21qMBT3YG/WBJjvbZuRFEb+5lEKytPkPVSm7Iz24rNen2vk2QzPR51IFvBzPot2TexgKvz8cQsDJqHJfrfCbSyksFiqqn3d/n34lW5Oi8moih1MqSAaAIifgmZkk2LJ6pakZzqcLmkgGgJfjWeRarO2aRXXR05kizibzqp6TEyX85lIKZV5Q9bybUajyOB3PaXZ+UQKOL7DQoz2squgiJ+Clpayap5SpCCJOLGY0Ofd6TKbyEDSWkCpzWNCoxmhEVdEnFjPgRe3+MPP5Ci5mS5qdvxFOEHExq7yFnVycx9/+9fvx51ddjlsOjOEj7/pDnD99StGxU2yx1dtUjGodunSZU/Qs+95Xv4zvf/3+Ze8Fe6P41q9fUnSdyWQeW/zulu6xGS7lyopLcz7D4p5b/hh7r7oan/jmowiEe7Fw8Q14/X5Fxy8WKijxgqYjaKqJvsAWFH92y45d+PTD35P/TVLKv2C2yiNRrKDX42zq/gBAFEWQCrtqqVJV8Xl/8tDX0Ts4hPff96D8Xl9sS1P3li5xcPu6XLQoSU1VcxRFIRTta/l6M9lSS6InJycBALFYDD7fxn3YtILBnTq/ffpJHHjLDfjyB+/AmWPPIdI/gD+65Ta87b23Kj5HusxhyOdS/PlmUUV0tsI31WiZn76A2689CMbhwI79B/GnH/o4BrZsVXx8usWuFkEQmJ+fx8LCAgKBAGKxGKLR6Jrjz3kFY9h1Fi/O4BePPYKbbrsD7/7LD+DcqZN4+HOfBONw4IZ3vUfROZSMmbeDKqKVDG3W2bH/ED7wha9gaNsY2GQcP/q7v8U9t7wTD/7sV/CFworOka3wEEQJFLlcUDabxezsLERRhCAIEEVx2Wun83e1QCaTQSaTwe7duzE4OLjsPJIkoZk2pSSJGL98Ard++OMAgLHL9uHiuUn84rFHFIvWunWviuhCVXn/9tB1N8qvt2IPdh04grve/vv41U9/gHe+7y8VnUMCUOSFVZMDHMdhYWFh3eMYZvXoGs+vLknNzjAFo32Ibd+57L3h8R14/snHFZ+D1HhSS5XuldjGr9Hl8WBk527MT19o+5rrNbQIggBFUWv+f5dr7ediMy3g3QevwNyF88vem39jCtGhYcXn0HrOWpUSTbYxx8pVK7h0/hz2HL6q7Wv6fD5ceeWVIElSFlv/DwCmp6eRTqcBANFoFKOjo/B61x5rDrkYlPLKaqqbbrsDd9/yTvzo77+Cq99xE86dOoGnvv8o7rz3S4q/T8il7Vi+KqK9DuW/xn/84mdw5A/ejt6hYWSSCfzw7x5EKZ/DDe96r+JzEAA8a5QAmqZB0+t/JZIkEYlEMDo6ummrO+RiMJdX1pPYvu8APvrVb+E799+HH/zvB9AX24L3ffxeXHfTuxUdDwBBjUWrMnvFljk8PZ1Q9Nn7P3wnzh47ihybgj8UwY79h3DLBz+KLSuecRsRcNJ467Zo0/fZTD86X+Xx5IV409doBZ+DxttGm/8+zaBKifY7aVAEoajl+OH7/77t67VazSmVDAA9Dhp9HgeWisoHTlplLOjR/BqqNMZIgsAWv3ad/ZWM6DAECgA7wz2aX8NJkbp8H9UmNcaC+kyg+x10S6NirdDndWou4UB/AAylfQSNaleoB/Zpza6I9qWskYk+P9y0NiJiPheGNRz2bETVb3CwPwBaw57/YI9Tl5mrRhwUiatjYThU/l4RtwOHB4KqnnMjVBXtYSjs71M2NdcsTorEwf6AJufejICTwbUjEdVKdr/XiWtioVVDuFqiSXDgq8kczibUCydiSALXbolo3tfcjKog4uWlLKZbDH6gCAJ7oz7dQ30BLaNA0wW8vGSOKNCVLBUqeD1VwGJRWQgQRRAY8buxM+yFtwPB+4DGcd2ZCofj8yxYg8d1r0e+ymM2V0a6XFt/VXozeJEkav3wkJNB2O1AzOfSpWW9Ebqs1Lj45jolJfPIJAEM+9wYD3q6aqWGUiRJ6tj6qo3Qfe1VolQFW+aQqXAQRAkgACdFIeR6c+2VxwFnF6+9Mir2akqL0J0Pvy7GqOXCFt0kS0tLePnll5FMJiEI+q4caYeuFp3P5zE/Pw9RbH4tslbE43EkEgmcOnUK2aw2q1K0oGu3tjh79iwWFxcB1ErR3r17QTUR/60FgiAgmUwCqMWfBQKdGalrha4t0SzLyq9TqRROnjwJjuvMiso6yWRSrl2i0WhT89udpmvvdOXzL5vN4sSJE6hUtF+Qth5LS0vy62hU24gQtTGMaJIk4fP5OlaqV1bbwWCwI/fRKl35jBYEQe7GuFwuOJ1OUBSFPXv2dOyeGqvt3t5eQ1XbQJeWaFEUEY1GMTExAYIgkMlkkEqlkM+ru8C+GeLx3wUK9vW1vm6sU3SlaIZhsHfvXkQiEcRiMfn9ubm5jtxPY7VN07Thqm2gS0U30t/fL1eTCwsLay6h0ZpUKiW3GYzW2q7T9XfMMAz6+/sB1EpWY8tXLxqrbaO1tut0vWgAGB7+3Rqm2dlZXcebBUFAIlFbnEDTNEKhkG7XVhNDiPb5fPISmnw+r+vQYzqdlqttI7a26xjmrhtLtZ6NssZHhRFb23UMI7qvr09eQLe0tKTLwIkoiqaotgEDiaYoCgMDAwBqAubn5zW/ZmNr28jVNmAg0cDq6lvrRpkZWtt1DCXa4/HIgxWlUkle1K4FjdU2RVEIh5Xtr9KtGEo0sLqrpRXpdFoenDF6tQ0YUHRvby8cjloYcDKZ1Gza0shTkmthONEkScrbRUmSpElXy2zVNmBA0QAwNDQkv56bm1M9pqyx2o5EIh0PYVIDQ4p2uVzo7e0FAFSrVXlmSS2MPiW5FoYUDSwv1Wo2ykRRlEWbpdoGDCw6HA7D7a4tik+n0ygW1dnzmmVZ01XbgIFFEwSx6lmtBmZrbdcxrGgAGBgYkPu38/Pzba+caGxt1zefMwuGFu1wOORSx/N820EJLMvKkyVmqrYBg4sG2p++lCRJrgnM2Nqu05Xhvs3g9/vh9XpRKBSQzWaRy+U23edzJc8++yxCoRB4ngdBECAIwjSt7TqGL9EEQbQ1/k0QBGiaRjweRzqdBkEQ8Pv9SCaTHQlE1ArDiwZqkaL15+ni4mLTghr37BZFESzL4uzZsx0LL9YCU4imaVqOFBVFccNd+Ndirc3ZR0ZGMDIyosr9dQOmEA20Fym6UvTw8DDGx8dVu7duwDSie3p65PXK5XIZpZLyTd8GBgYQi8VA0zQGBgawY8cOrW6zY5hqs5p4PI5yuYyBgYE1E6VshiiKcqvbbJhKdLfu8dUNmKbqBppPY2QlTCXaZn0MPzK2GbkKj1S5inSZQ6EqQJAkkERtM9mgi0HI5dA8FVE3YKpndB1BlHApp3z/0R4HhbGAF1sD7o5vzqoVphOdLFVxfIFFvok0inXqm79rmfW1U5hK9Jl4DpOp9re/2OJ341B/QNcd8rXGNKJfXGDxRqa1nfHXIupx4OrhsGlkm+KBdCaeVVUyAMSLVRybZ1U9ZycxvOhkqYrJVEGTc8/ly5jOqBN02GkMLVoQJRzXuNSdWsrKKRSMjKFFX8yWkOe0lcCJEs5pVGPoiaFFT7HNCXjiu9/Gf3/rVfiTiVH89bv/CGd/e1TRcdPZYi0thIExrOhMhWsq+85vHv9n/MN9n8bNd/4VvvyTJ7HnyFX43B23Ij53adNjq4KEeYW5pLsVw4pOlZrbw+Rn3/4/uPHmW/CH77kVsfEd+Iu770VkYAi/eOwRZddTMMLWzRhWdLqsPK8zV63i/JlTOHDN9cve33/N9Zg88VuF17NFd4Rmhjhz6RREQUAg0rvs/WAkCjahLOg/XzV2RKhhRSvJPr+SlfPVEiRA4Ry2aPABRMOKJpsIMvCFwiApCmwivuz9TDKBYETZQjqjBzUYVrSniRS/jMOB8csn8NKzzyx7/9Szz2DXwSOqX68bMWzgQdDF4GJOeZfnptvuwFf+519hfO8Edh04gqe+/ygS87N4+5/8meLrGRnDig65mktQes2//2Pk2DR+8PUHkI4vYWTHLtz9jUfRNxzb/OAWrtdtGHaaUpIkPDEV12UcmiSAd4z1w2ng6tuwd04QBEaDHl2uFfO5DS0ZMLBoABgNuMFoHBhAANge8mp6DT0wtGgnTWGiz6/pNXaGvYZviAEGFw0AWwMeDPY4NTm330ljT29zi+q7FcOLBoArBoOqx2Z7aApXD4ebGpjpZgzb6l4JJ4o4OpvGUlH5ZMd6+B00ro6F4WHMs1mNaUTXOZcu4Ew819pYOIAdYS/2RHymif6sYzrRAFCo8ng9XcBMpgRewdcjAAz7XNgZ7jFFw2stTCm6DieKmMuVkSpzYMsc8lX+zbVXBDwMhZCTQdDFYNjngos2TzW9FqYWbfM7TNHqttkcW7RFsEVbBFu0RTDsfHQr8Dwv70HmcrnkzHhWwFKiRVHE1NQUgNoO/lYSbamqu3H/bbUz63Q7lhLdmI3OFm1iGncFtEWbnHr13W7+DaNhOdH16tsu0SbHFm0R6lW3Ldrk1Eu0IAiaZ5TvJiwrGoAt2sxYtS9tOdGNo2NW6mJZTrRdoi2CLdoi2FW3RbBLtEWwRVuERtF21W1irBp8YDnRdtVtEWzRFsHuXlkEu0RbBFu0RbC7VxbB7l5ZBLvqtgi2aItgd68sgl2iLYIt2iKQJCmvv7KrbpNjxdUatmiLYIu2CJYUbcWls5YUbZdoi1AXLUmSZdZfWVK0FUfHLCnaioMmtmhbtHmxq26LYJdoi2CLtghWjBuzpGgrxo1ZUrRddVsEW7RFsLtXFsEu0RbBFm0R7O6VRbC7VxbBrrotgi3aItjdK4tgl2iLYEXRlsofXa1WMTk5CUEQUK1W5eBASZLgdrtx4MCBTt+iZlgqZaHD4YAkSUin06v+39atWztwR/phuap7bGxs1Xs0TaO/v78Dd6MflhPd09ODaDS67L2hoaFlLXEzYjnRADA6Oiq/JggCw8PDHbwbfbBUY6yRYrEIQRDAMAxcLlenb0dzLCvaaliy6rYitmiLYIu2CJYaMKkjSRLyVQFlQYAkATRJwOegwVDm/d1bRnRVEDGdKWIuX0GmzIFfow3aw1CIeBwYDXgQdjs6cJfaYfpWd1UQcTaRw3SmBKGJrxp00tgb9aPP69Tw7vTD1KIX8mWcWMygxLc+QzUa8GBvnw8Maexq3bSiJ5N5nEnkVDmX30HjLVvCcNHGHSY19s90HV5LqScZALJVHv92MYVKGzVDpzGd6HixgtNx9STXyVV5HF9gVT+vXphKNC+KOL6Q0ez8C4UKpjNFzc6vJaYSPZksoMhpG+x3aikL3oDhR6YRLYgSLigsbWeOPY/P3/lnuP3ag7h59xCO/vJfFV+HEyXMZEut3mbHMI3o2XwZVUFZSauUiti2+3Lc/snPtXStKdZ41bdpRsYW8mXFnz103Y04dN2NLV8rW+FR4gS4GeN0t0xTotkyp+v10jpfr11MIZoXReQ1boSthK3YonVH6bPZ6NdsB1OIttkcU4imOzDhQJOE7tdsB1O0uh0UCTdNKp6lKhUKWJi5IP976dJFXHjlNHoCQUSHYorOEXAyLd1rpzDN7NVzsynM5yuKPnv66LP49J//p1Xv3/Cu9+IDX3hQ0TneNhqFz2GccmIa0efSBZxayupyLTdN4h3jxlrCY4pnNACM+N2gdHpsjgY8+lxIRUwj2kGRiPndml+HALAtaIvuKJf1+sBo3BreHekxZKSJqUS7aQoTfX7Nzh9w0tgV6dHs/FpiKtEAsDXgwYgGVbiDJHDFYBAkYaz+cx3TiQaAwwMBxHzqrZB0UASu2RKG32B950ZM071aiSRJeC1VwCvJHMQ2vmHYxeDIYBA9Buozr4VpRdfJVDicWMgg1eS0Ik0S2B3pwY6QV843bWRML7pOqlTFFFvEXL4MfoMiHnTS2BasPec7MYauFZYR3UiuyoMtcyjzAiTUSq/fQSPoYkwltxFLirYi5vz52qzCFm0RLCG6lR18eZ7HwsICymXl0aXdjLE7hwq5dOkSlpaW4Pf7EYvF4PV6N/z80tISXn31VQiCAKfTiYMHD8Lt1n7CREssUaJTqRTy+Tzm5uYU9YlZlpVrgUqlgpMnTxq+ZJtetCAIyGRqC+9cLpeiklmtVpf9u1wu4+TJk6hUlEWwdCOmF82yLOo9yFAopKhEryVUFEUkEgnV708vTP+MbtyyORwOKzqmLpqmaXi9XpAkiYmJiWUbuhsN04tOpVLy61AopOiYUCiEvr4+zMzMgGVZAEChUIDP59PiFnXB1KIrlQoKhQIAwOfzgWGUTTPu2bNHPr4uenFx0dCijVsXKaCVaruRaDQqP9OXlpZg5NFiU4tupdpuhGEY+QdSqVTk1rsRMa3oxtwZFEUhEAi0dJ6+vj759eLioir31glMK7pQKMj94UAg0HKLube3Vz42Ho8bNn2SaUU3VtutPJ/r0DSN3t5eAADHcWtm2DECphXdbkOsETNU36YULQiC3C1yOBzweNpbWRGJREDTtZ5oIpEwZD5LU4rOZrPyszQcDrcd3EeSpJxCSRAEJJPJtu9Rb0wpWq3ncyON1ffS0pIq59QT04tupf+8FqFQCA5HbbP2ZDIJnudVOa9emE50tVpFPp8HUMtaV5fTLgRByNW3KIqIx+OqnFcvTCe6sbWtVmmu05i/0mjVt6lFq/V8ruP3++Wsd+l0elWAQjdjKtGSJMnPZ5IkWx72XA+CIORGmSRJhirVphJdLBbloIFAIKBJBlmjVt+mEq1ltV3H6/XKAzCZTMYwQYOmEq1F/3klBEEsK9VGGRI1jWhRFOVhT4ZhNo3dbgcjVt+mEZ3NZuUxaDWGPTfC7XbLYUX5fF4OV+pmTCNai9GwjTBaqTaNaD0aYo2snLrs9ngyU4jmOA7ZbG17SK/XC6dT+3ySTqcTwWAQAFAqleRh127FFKLrjTBAn2q7jpFa36YQrUe3ai2MFA5sKtEEQcjVqR6sDAdurFm6DcOLLpVK8uiUVsOeG2GU1rfhRXeq2q4TiUQMEQ5sWNHT09NIp9O6959XYpRwYMOKTiQSOHnyJNLpNHw+H4LBYMeWtRqh9W1Y0T09te2UBUFALpcDy7I4duwYXnrpJd3vJRwOd304sGFFrzVp4XA4sGvXLt3vxQjhwIYVXS/RdUiSxL59++RQH72pD4muvK9uwbAL4Xt6ekCSpNzK3bNnD/x+7Xbf34xQKIQjR4507WJ5Q+8FKkkSCoUCeJ7XdaDEiBhatI1yDPuMtmkOwz6jux1eFJEuc0iXOWQrPHhRBEDASZEIuGiEnAwCLka3ZCx21a0ymQqHqXQRM9kShE3+tC6axGjAg21BD9wa59LqWtFLhQoWCxWwFQ5smQP3ZnoEmiQQcDIIuRj0eRzo9zq7IucFJ4g4Fc9iOlNq+liSqCVn0zJ/R1eJFiUJU2wRU+kC8pyy0SUPQ2Es6MF40AuqQzmdE8UKjs2zitMar0fYxeDKoRA8jPqlu2tEs2UOxxdYZCqtLUftcVA4PBBExK3O6kmlLBbKeG423VbKpUbcNInrtkTgVTn9UleIvsAWcXIxAzVuZG/Uh51hfUan0qUqnrmYhKDyX9DLUPiDrb1wUOp1ijrevTqfLuCESpIB4HQ8h1eTOZXOtj6CKOHYAqu6ZAAocAJeUjkXdkdFLxYqqn8hADibyONSrvlGUVPXSOaQr2o3S3UxW8J8Xr11XR0TzQkiXlxgNTv/ycUsyrw2Iiq8gPNp7VdnnE2oVzN1bMDkTCLXdit1I6qCiFNLWVw5pH7UyRuZkuLG1xOP/SN+8dgjiM9eBABs2b4L77nrQzh03Y2bHpup8EgUq+j1tN/A7IjoiiDijUxR0Wd//I2v4vmnHsfs1Dk4XC7sOngE//Uj92B4bPumx87myihygurdFaX3DgCR/kH8l4/cjcGRbQCAX/30B/jiXe/Dl378JEZ2bD53Pp0pqiK6I1X3dKaouEScOfYc/t2f3ob7vvcv+PTD/wSRF3Dv7begXNz8jy2h1qLf9HNNdDwqvICCwj4+AFxx49tx+Pq3Ymh0HEOj47j1Qx+Dy+PFay8dV3R8sqTO9hkdKdGzOeWNjE8+9N1l/77rvgfwF1fvw/kzp3D5Fb+36fGXciVcHt14jrhSqeDUqVMYHh7GwMDAhiHDbKW5rLWNCIKA5574GcrFInYdOKLomDwngBNEMG12tXQXLUoSMm38sYq5WivdFwgq+nyBE1AVxA37pCRJolAo4LXXXsPU1BQGBwcxPDy8ZkadbAsDOtOTr+DuW25CtVKBy+PFR7/2LWzZvlPx8fkqj1CbA0G6i85U+JZHkSRJwre/8L+w5/CVGNm5W/FxbJlDn3f5wrtqtYrTp09DFMVlVTfP87h48SJmZ2dx/fXXrzpXK/c+NDqOL//kKRSyWTz/5M/xtY99EPf+3x8rlr3Z5IgSdBddauL5tpKHPns3pidfwee++9PmrrlGN4sgiA131F/vud3KnAPjcGBw6ygAYPu+/Th3+iR+/shDuPPev1F0vBoTHbo3xqQWx8Ae+uw9OPb0k/jMIz9EZGCouWuuccnGPx5FUav+mAzDrClblelECeCa2KNMjWvqXqKpJn+dkiThoc/egxd++QQ+88gP0R8bafqa5BqzWhRF4frrrwdBECAIAs888wwEQQDDMBgZGcHw8PCaJSnoUpZpp8537r8PB6+7Eb0DQygV8vj14/+MMy88i0988zuKjndSpCrdQ91F9zQ5K/PNe+/Gv/3LT/Cxr/8D3N4epOO1hWwenw9Ol7LEoD7H6j9UXXAdp9OJ/v5+xGIxORh/7XPRoEkCvMKHNZuM4ysf/QDS8SV4fD5s3bUHn/jmd7D/mtXP/7Vo9oe1Hh2ZvfrZ6wtyIMFm3Lx77Wr6rs8/gBvf/Z83PZ4kgHfuGNg0ZEcQBMUrMY8vsC0FGLTC4YEAtgba21ge6FA/Oux2YLGgLKHnj16da+taQaeyuKxmltuOBb26iHaQBGI+ddIZd2RkbGtAv1zMapSGlYRcDHp1CHAYC6kXNdMR0UM9LrhUnFRfD4YksMWvzRKdQwMBUBpGLvkcNHapGEDREdEkQWBPr/ZRIDvDPaA1Wkrb46BxeVSbJUAEas9mNWPgOjYfPRr0IqrCrMx6hFwMdoa12yYSALaHvBgLqv9oODwYRFjlR0NHI0wODwTg1KAKp0kChweCuoQBH+gPYHtInR8USQBXDAYx4le/DdPx4EC2zOHXF5OoqhRGSRMEro6FVZnDbYaFfBkvLmZQbjGYIuRicHggCL9Tm45Qx0UDQLbC4egci1y1vcwzXobClUNBhFz6Sq5TFUS8nirgjUwRFUGZcJ+DxnjIg9GAR9MaqCtEA7WoyleSObyeKrQ0Gj4W9GBv1KdZ46sZREnCbK6MRLEKtsIhU+HkWS+aJBB8c6XJQI8TUY/221kCXSS6Tr7KY4otYjpT3HT0jCYJjPjdGAt64HeqM1SoFYIogSCg26K6lXSd6DqCKCFdriJd5pCp8Ki+WRUyFImAk0bIVSsV3VCCjUDXirZRF7s4qEg3lxlbtErwPI8XXngBMzMzKJX0mdlqBtOIZlkWZ86cQS6n/bqrtUgmkygWizh//jxmZmY6cg8bYYqtLRYXF3H27FkAtenG3buVBw6qRePOvo1pGLoFU5ToSCQizycvLi6C41oPJ24FjuPk3QIdDkdXboVlCtE0TWNwcBBALf/V/Py8rtdPJBJyQ6yvr68rttpYiSlEA8Dw8LD8enZ2VtcWcLdX24CJRHs8Hnlj9nK5rNvGq417dDudzo5uU7kRphENrC7VehCPx7u+2gZMJjoSici7+6ZSKRQVrLhsFyNU24DJRBMEoWuprlarcrXtcrm6dmdfwGSiAWBwcFBOuTA/Pw+eb2+OeyMaS3N/f3/XVtuACUUzDCPnuBAEQdMcF0aptgETigb06WpVKhV5NabH49E0X7UamFK0z+eTuzmFQkGTDHMrS3M3V9uASUUDQCwWk19r0SgzUrUNmFh0NBqFw1ELEkwkEnJaQzUolUrL0hh3e7UNmFg0SZIYGqqtxJQkCXNz7S3Wa2Rla9sImFY0AAwNDcnPzrm5OdXyRhqt2gZMLtrpdMqJxziOUyUbbLFYlLO/+3y+NXcu6kZMLRpQf/zbiKUZsIDoQCAgN5ay2azciGqGarUqj5sbVbQpQok2giAIxGIxTE5OAqiVapZlkclksG/fPkXn4HkeR48eRU9PDxiGgcPhgMvl6lh6xFYwvWig1jKenZ0FRVFYWlqCKIpNTUA4nbVlM/VnM1ALGZqZmUF/f7/8/7sZ04tOJBKYmZlZJglobs8SiqLAMMyyWLR8Po9yuYxQKGQI0aZ/RjudzjXnpZtNKr5SJkVRmJiY6OqpyUZML9rn8+Hw4cOrukHNlGhguWiSJDExMYFAIKDKPeqB6UUDgNvtxqFDh+TSR1EUIpFIU+fYvXs3xsfH4fF4sG/fvq4M6d0ISy2y43keLMsiGAxuuDvgRkiS1PUzVWthKdFWxhJVt40tek3MWMmZvh+9GalSFfP5CtgyB7bCyZvMUATgf3OvkV63A0M+V8e2pVADyz6jZzJFnEsXFSdDcVIktgU82BH2qpozUi8sJ7rA8XhxIYN4sbU0Qy6KxMGBAAZ7jDPODVhM9EK+jBfmWPAqfOXxoAf7+40zYGIZ0fP5Mp6fTauW1RaobUd9eCCo4hm1w3gPmxao7UyormQAmM6UMJnMb/7BLsD0oiVJwvGFjGoZ21fySjKHbBsJ2/TC9KLPpQtIl7UTIUrA8YX182d1C6YWLUoSzrWQ5/nH3/gqbt49hIc//ylFn0+XOSRabMXrhalFz+fLTeeoPvfySTz1/UexdddlTR03xWqfOLwdTC36UhNZbQGgVCjgwf/xftz52S+hx99c12kuX4bYxR0YU4tmm3w2P3Tv3Th8w1ux/+rrmr6WKLWWiVYvTDvWXRXEphJ6//rnP8XU2ZfxxR8+3vI102VOtcxzamNa0WtlmF2PxPwsHv78p/Cpbz0Gh7P1oc1mrqk3ph0ZY8scnp5OKPrs0V/+K/7m/f8NZEMcmSgItfyVJIl/OvWGohiznWEv9mqUIqldTFuim8lqO/F71+KB//f0sve+dveHMDy2Hf/x9rsUBxI2m0lXT0wr2sNQIABFw57unp5VGeZdbg98wVBTmed9TWbS1RPTtropkkBAo9RC6xHq0oYYYOJnNACcXMxgitV+UzmgFpjwH7Z376J405ZoANimQabZ9dAzg24rmFp08M1MOnowqkGOSjUxtWgAuKxX+7VR2wJueJnubYgBFhDd73Vim4bVqpsmsa9L+86NmF40AOyL+tHDNLeoTgm1PM9BMAaICu3+O1QBhiLxli0ReFSUTaCWArjP2/1rowGTd69WUuIFvDCXRrLUXsSJkyJxeCCAAQOF/FpKNFCLITuXLuBsIgehhW8+7HPhQJ8fTlr9R4GWWE50nRIv4A22iAuZ4qbJvUkCGPbVstpG3J3JTd0ulhVdR5Sk2rqr+torXoSEWsri2torGiGXw5DLcBqxvGirYOyfqY1ibNEWwRZtEWzRFsEWbRFs0RbBFm0RbNEWwRZtEWzRFsEWbRFs0RbBFm0RbNEWwRZtEWzRFsEWbRFs0RbBFm0RbNEWwRZtEWzRFsEWbRFs0RbBFm0RbNEWwRZtEWzRFsEWbRH+P58lMKmjWA2KAAAAAElFTkSuQmCC"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 5
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 在有向图中寻找割点和桥",
   "id": "dcdc3fc07b7f7874"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "**如何判断割点？**\n",
    "\n",
    "我们不妨假设两种情况：\n",
    "\n",
    "1.   节点$x$ 不是深度优先遍历树的根节点（root节点）\n",
    "\n",
    "![image](./assets/img_4.png)\n",
    "\n",
    "如上图中左测图和中间图中所示，如果删除节点$x$，那么图就被分割为了**x的祖先** 和 **x的儿子** 两个部分，所以显然在这种情况下，**节点$x$ 是一个割点**。\n",
    "\n",
    "而在右图中，即使删除了节点$x$，原图的连通性仍然没有改变，这种情况下**节点$x$ 不是一个割点**\n",
    "\n",
    "2. 节点是深度优先遍历树的根节点\n",
    "\n",
    "![image](./assets/img_5.png)\n",
    "\n",
    "所以判断割点的条件就是：\n",
    "\n",
    "1.   节点$x$ 是根节点，且有两个或以上的子节点\n",
    "2.   节点$x$ 不是根节点，且满足 low[y] >= dfn[x]，其中$y$ 表示$x$ 的子节点"
   ],
   "id": "248b499b2d12b4e3"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 如何判断桥?\n",
    "\n",
    "![image](./assets/img_6.png)\n",
    "\n",
    "由上图可以看到只有在 $low[y]>dfn[x]$ 的时候，删除掉节点$x$和节点$y$之间的边可以改变节点的连通性，所以只有左侧的情况是一个**桥**。\n",
    "\n",
    "![image](./assets/img_7.png)"
   ],
   "id": "5bebd2ecb7cf7cfc"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:14.911495Z",
     "start_time": "2024-10-17T03:38:14.896520Z"
    }
   },
   "cell_type": "code",
   "source": [
    "class UndirectedGraph:\n",
    "    def __init__(self, vertices):\n",
    "        self.V = vertices\n",
    "        self.graph = defaultdict(list)\n",
    "        self.time = 0\n",
    "\n",
    "    def add_edge(self, u, v):\n",
    "        self.graph[u].append(v)\n",
    "        self.graph[v].append(u)\n",
    "\n",
    "    def _tarjan_ap_bridge(self, u, visited, parent, disc, low, cn, bridges):\n",
    "        \"\"\"\n",
    "        使用深度优先遍历寻找割点\n",
    "        :param u: 当前遍历的节点\n",
    "        :param visited: 记录是否已经遍历\n",
    "        :param parent: 在深度遍历树中当前节点u的父节点\n",
    "        :param low: 当前节点u能追溯到最早的祖先节点, 也就是TNA(topmost neighboring ancestor)\n",
    "        :param disc: dfs遍历到当前节点u的时间, 即遍历的第几个节点\n",
    "        :param cn: 用于标记该节点是否是一个割点(cut node)\n",
    "        :param bridges: 用于记录桥\n",
    "        \"\"\"\n",
    "        children = 0\n",
    "        visited[u] = True\n",
    "        disc[u] = low[u] = self.time\n",
    "        self.time += 1\n",
    "\n",
    "        for v in self.graph[u]:\n",
    "            if not visited[v]:\n",
    "                parent[v] = u\n",
    "                children += 1\n",
    "                self._tarjan_ap_bridge(v, visited, parent, disc, low, cn, bridges)\n",
    "\n",
    "                low[u] = min(low[u], low[v])\n",
    "\n",
    "                # 割点条件1：u是根节点，且有两个或以上的子节点\n",
    "                if parent[u] is None and children > 1:\n",
    "                    cn[u] = True\n",
    "\n",
    "                # 割点条件2：u不是根节点，且满足 low[v] >= disc[u]\n",
    "                if parent[u] is not None and low[v] >= disc[u]:\n",
    "                    cn[u] = True\n",
    "\n",
    "                # 如果 u 到 v 的边是桥\n",
    "                if low[v] > disc[u]:\n",
    "                    bridges.append((u, v))\n",
    "\n",
    "            elif v != parent[u]:\n",
    "                low[u] = min(low[u], disc[v])\n",
    "\n",
    "    def find_cn_and_bridges(self):\n",
    "        visited = [False] * self.V  # 初始化节点的属性 [False, False, False, False, False]\n",
    "        disc = [-1] * self.V\n",
    "        low = [-1] * self.V\n",
    "        parent = [None] * self.V\n",
    "        cn = [False] * self.V  # 存储割点\n",
    "        bridges = []\n",
    "\n",
    "        for i in range(self.V):\n",
    "            if not visited[i]:\n",
    "                self._tarjan_ap_bridge(i, visited, parent, disc, low, cn, bridges)\n",
    "\n",
    "        return [i for i, is_cn in enumerate(cn) if is_cn], bridges"
   ],
   "id": "6f606c3694aff026",
   "outputs": [],
   "execution_count": 6
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:27.007026Z",
     "start_time": "2024-10-17T03:38:26.993750Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 示例使用\n",
    "g = UndirectedGraph(7)\n",
    "edges = [(0, 1), (0, 5), (0, 6), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (5, 6)]\n",
    "for i, j in edges:\n",
    "    g.add_edge(i, j)\n",
    "\n",
    "cns, bridges = g.find_cn_and_bridges()\n",
    "print(\"割点:\", cns)\n",
    "print(\"桥:\", bridges)"
   ],
   "id": "f5be5e490f8df81e",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "割点: [0, 1]\n",
      "桥: [(0, 1)]\n"
     ]
    }
   ],
   "execution_count": 7
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-10-17T03:38:31.428268Z",
     "start_time": "2024-10-17T03:38:31.381609Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 绘图\n",
    "n_vertices = 7\n",
    "g = ig.Graph(n_vertices, edges)\n",
    "id_list = list(range(0, 7))\n",
    "g.vs[\"id\"] = id_list\n",
    "fig, ax = plt.subplots(figsize=(5, 5))\n",
    "ig.plot(\n",
    "    g,\n",
    "    target=ax,\n",
    "    # layout=\"circle\",  # print nodes in a circular layout\n",
    "    vertex_size=0.3,\n",
    "    # vertex_frame_width=4.0,\n",
    "    vertex_color=\"lightblue\",\n",
    "    vertex_frame_color=\"white\",\n",
    "    vertex_label=g.vs[\"id\"],\n",
    "    vertex_label_size=9.0,\n",
    "    edge_color=\"gray\",\n",
    "    edge_arrow_size=0.01,\n",
    "    margin=40\n",
    ")\n",
    "plt.show()"
   ],
   "id": "cae5c6e118919567",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Figure size 500x500 with 1 Axes>"
      ],
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWcAAAGVCAYAAAAi4jCfAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAAA7SUlEQVR4nO3deZRk2V0f+O99S+xbRu6ZUfuelVldS0stdbcEjIRGlmHGIDMMGhjZshF4EYJjhmGEgTGaM2fM2DMgGYNlCeyxx4gZBGNxjMCyBahBjaSq6lZlbV1VWUtWZkTusa8v4t35IytCVZWVlUu8fO9FxPdzTp/TGZH14taS37jxe/f+rpBSShARkasoTg+AiIg2YjgTEbkQw5mIyIUYzkRELsRwJiJyIYYzEZELMZyJiFyI4UxE5EIMZyIiF2I4ExG5EMOZiMiFGM5ERC7EcCYiciGGMxGRCzGciYhciOFMRORCDGciIhdiOBMRuRDDmYjIhRjOREQuxHAmInIhhjMRkQsxnImIXIjhTETkQgxnIiIXYjgTEblQx4SzlBKmlJs+b0oJ+ZzniYg6ieb0AJ7HlBKKEKibJtIVo/VfpW62gloVAn5dRZ9XR59fR8yrQ1VE69cSEXUiIV023WwORwKYy5VxN1PCWsXY0TWGAh4cjgUxGvJCAgxpIuo4rgpnU0o0pMRbqwXcz5ZRa5htXc+vKTgUC+JYXxBCMKSJqHO4IpyllBBCYKFQweXFLCr19kL5aSFdxYujMfT5dAgGNBF1AMfD2Xx0o+/NxRxmc+U9fa2jfUFMDoYBcBZNRO7maDibUsJomHjt4Rpytbotrzng9+DlRB8UIRjQRORajoWzKSVqDRN/NruKotGw9bX7fDretS/OgCYi13JknbOUEg1T4rWHa7YHMwCkKwa+Npe2/XWJiLbLkXAWQuCNxSzyNpUynmWlXMP1lTw3rhCRK9kezqaUmM+XMZev2P3SG9xeKyJTNZ6785CIyAm2hrOUEnVzfWWGG0gAF1NZp4dBRLSB7TPn6yt5VNvcXGKlfK2OO+kiZ89E5Cq2hrMpsedrmXfjXqYErtkgIjexLZxNKfEgV0LddN8MtWg0sFiqcvZMRK5hWzgrQuBupmTXy+3Y3XSJa56JyDVsC+dKvYFc1bmlc1tZ4syZiFzElnA2pcRaeWdtP7ejWinj773vZfzI2062fS1TAnkXv3kQUW+xbeac3mFP5u34/Kf+d/QPj1p2vbUK1zwTkTvYEs6KEMhUrQ3nu9eu4PJXv4Lv++jHLLtmpmJw1QYRuYJtx1SVLeyh0ajX8es//z/gR3/+f7XsmgBQqjfY75mIXMG2skbDwnLBF3/rN3DgxClMvvSyZdcEwJIGEbmGqw94fZaF2fv4o3/3r/BPfu8/Oj0UIqI9Y1s4qxaVC65f/Dpya2v4ye/9LgBA3TBQLuTxt159AT/7z/8Vjp05t+trc50zEbmFbc32//zhKpZKtbavU62UUcrnW1+/9cZF/Nonfgqf+tJrCMf6oOn6rq99MOrHueEo685E5DhbZs6mlOjz6ZaEs9fnh9fnb30disYAIdA3ONT2tWM+HRLgig0icpwtM2dTSqQKFXw9mdnrl2rLf3FgADHf7mfeRERWsW2dc9znseOldk0AiHg77v4oEXUp25bS+XUVEY97w28o6OUNQSJyDVtbhh6KBex6uR07HPOjWCohlUqh0bD/0FkiosfZ2jL0QNQPzYWz04CmYiTow8PZWdy8eROvv/46ZmZmUKk4f84hEfUmW+sMqhDYH/W7rq/zoVgAjYaJxcVFAIBhGJidncXs7CwGBgaQSCQQi8W4xI6IbGPbOmdg/YBXw5T4j/eWUXPJOYIhXcV7Dg5CEUAul8P8/DyWlpbw9B9LIBBAIpHA8PAwNM29tXMi6g62hjOwXntO5iv4Ripj58tu6jv39yPm05+4GVitVpFMJpFMJlGrPbk2W1VVjI6OYnx8HIGAe2voRNTZbA/npr+cTyNZcLame7QviKnB8KblCtM0sby8jPn5eWSz2Q3Px+NxjI+Po7+/nyUPIrKUI+HcLG/86YMVFCxsJboTcZ+Od+3v33bPj3w+j/n5eSwuLsI0nyzJ+Hw+jI+PY3R0FHob28eJiJocmzmbUqLaMPGnD1ZRrtsb0FGvhnfv74cmxI5nvIZhIJVKYX5+fsNqDkVRMDw8jEQigVAoZOWQiajHOBbOwLcD+rXZVdtm0HGfjlcScaiKaGvTiZQSq6urmJubQzqd3vB8NBpFIpHAwMAAFMW2FYtE1CUcDWdgPaAbpsTlxSzm83tbgz4cC2BqMAJFwNIacbFYxPz8PBYWFjZsYPF6vRgbG8PY2Bg8HndvYX+Wx/95sK5OZB/HwxlYDwAhBObzZby5mEPV4mV2AV3FhZEoBgPe1mvthXq9joWFBczPz6NUenIttxACQ0NDGB8fRzQa3ZPXb5cpZevTRMOUyFYNVOomTCkhxPo69ZBHQ+jRNvzmPx2GNpH1XBHOTaaUqJsSN1cLeJAtwTDbG5pXVXAoFsCJeAhC2NdMX0qJdDqN+fl5rKysbHg+HA4jkUhgcHAQqqraMqbNNP/6TQk8zJexXKohUzGQr9U3/TWaIhDz6oj5dOwL+9Dn9zwR7ETUPleFM/BUWOTKuJspIlPdPCiepd/vwZFYAGNhX6s3s1Ozu3K53FozXa8/+fvQdb21Ztrn89k6ruYniGKtjjuZImaz5V2/Gca8Gg7HgtgX8dv6JkjUzVwXzo9rzsZqDRPpSg3pioFMxUD50UdtYP2jtl9X0efTEfNqiPl0eFTVdTO5RqOBpaUlzM3NoVAobHh+cHAQ4+PjtmwTN6WEKSWuLOVwP1u27LpeVcELQxEkIv49LR8R9QJXh/PjpJSQ2HxWVqnWkM9lUSgUsH//fsfLBZuRUiKXy2Fubg7Ly8sbtokHg0GMj4/v6TbxxWIFlxeyKNf3Zgv9eMiHcyNRaG2uiCHqZR0Tzlu5ceMGFhYWAADnz5937U23xz1vm7imaRgZGbFsm3jzr/nKUg4zNjSe8qoK3jHeh7hP5wyaaBe6Jpzn5+dx69YtAMDRo0exb98+h0e0fdvZJp5IJBCPx3cVdM2/4oupDB7u8XLFx6kCeMd4H4YCXgY00Q51TTjn83lcvHgRADA0NITTp087PKLded42cb/fj/HxcYyMjOx4m/jFVAazOevqy9ulCODVRD/ifp0lDqId6JpwNk0Tr732GkzThM/nwzvf+U6nh9QWwzBaJY9nbRNvljy22iYu5frSxBurG29C2kVTBN57cBB+TeEMmmibuiacAeDy5cutssArr7zSkTvynialxMrKCubn55+5TTwWi2F8fPyZ28RNKZGv1fGV+ytw+i95wO/Bu/f3OzwKos7RVV3jI5FIK5xzuRwGBgYcHlH7hBAYHBzE4ODgM7eJZzIZZDKZTbeJX0xlHA9mAFgp1zCTLuJwLMDZM9E2dNXMeWlpCdeuXQMAHDhwAIcPH3Z4RHtjq23io6OjOHb8OG6tFnDdwXLG01Qh8L7Dg/CpLG8QbaXrZs5NuVzOwZHsLU3TkEgkMD4+vmGbuJQSmqZBSok7maLDI31SQ0rcSRcxORB2eihErtdV4ezz+eDxeFCr1ZDL5bp+l5oQAvF4HPF4HOVyGfPz80ilUhgdG8dcvoJaw30fih5kSzg9EEb3/q0QWaPrGg03Z8+NRmPDR/5u5vf7cfToUbz88ssI+H2uO+G8qdaQeJgrt7bfE9GzdW04A91d2tiMqqoo1OpIVwynh7Kp2VyZa56JttBVZQ1gYziPjo46OBr7mVJitVzb+hu3wahV8dlP/hyufO015NJriA+P4K/97b+L93zwh9q6brpsdH3JiahdXRfO4fC3bzb14sxZAJbNmhv1BmKDQ/jF3/odDO87gNvfuoz/5aM/jP7hUZx99Tt3fd26lCgajVbTfiLaqOvKGpqmIRgMAgAKhcKGHsrdTgiBjEXh7AsE8EM/8TMY2X8QQggcP3sBky+9jBuXv9H2tdcqBuvORM/RdeEM4ImOdPl83sGROCP3nFNM2lGrVnD7yps4eHyi7Wvlqu6tiRO5QVeGc6/fFKy3ebzXs0gp8ev/8KcxeuAQXnrfB9q+Xt2UXE5H9BxdWfR7PJx7bea8F6UCKSU+8z//LObvzeAXf+t3NvTw2A2TNwSJnqsrZ86BQKB1Esqz+iN3M6uXqEkp8S9/6RO4Pf0GfuFzv41gOLL1L9oGRYgNp8AQ0bd1ZTgLIVqz51qttqHlZrfTFesC+rOf/ARuXv4mfvFzn0coGrPsupoiXNGQiciturKsAayXNpotNnO5nO2nWzsp4tWwWm7/htvS/Bz+6N/9a+geL378PW9vPf7u7/0gfuwf/eO2rh317uywAKJe09Xh3JTL5TA0NOTgaOwjpUTMp1sSzkPjCXzhZtKCUW3Ek1GInq8ryxpA767YkAD6XD4r1RSBoN618wIiS3RtOHs8nlYpI5/PbziPr1spQmAg4O4TYOI+d795ELlB14Yz8O3Zs2maKBbd1dt4LwV0Df1+9wb0wWiAuwOJttAT4Qz0VmnDlBJHYgGnh/FMPlXBWNjHejPRFhjOXUgRAmNhH7yq+/56D8YC3BlItA3u++m1UCgUau1C66VwBta70x2PB50exhN0ReBILMidgUTb0NXhrKoqQqEQAKBUKsEweqfZjhACR/uC6HPRzbczQxHoKoOZaDu6OpyB3u6zIQG8bTQGCzcM7tpI0IsD0QBrzUTb1FPh3GuljWKhgICm4LTDp117VIHzI1H20iDaAYZzl1pYWMClS5cwMzODY/GQY6s3NEXg1UQ/PKrCWjPRDnT9Ni2/3w9d12EYBnK5XNefXSelxN27dzE7OwsAmJubQyQSwQvDw5CAradya4rAK4k4Il6N5QyiHer6mbMQonWuoGEYXd2hrl6vY3p6uhXMADA2NobBwUEAwNnhKE71h2wZi19T8R37+tHnYw8Not3o+pkzsF7aWFtbA7Be2vD7/Q6PyHrlchnT09OtnZBCCBw7dgzj4+NPfN/J/hCGg15cXMigUGvsyVgORQOYGopAEdb3lybqFT0Tzk25XA7Dw8MOjsZ66XQa165day0V1DQNp0+fRjwe3/C9QgjEfDree3AQ15bzuJMuWtZXOaCrOD8cxVDQ2/XlI6K91pPh3E2SySRu3brVWgkRCAQwNTWFQGDzG4DN2ezkYBjH40HczZRwP1tCub675lCDAQ+OxIIYDXlbQc9gJmpPT4Szruvw+/0ol8utDnVWnIPnJNM0cefOHczPz7cei8fjmJiYgK5vb+OJEAJeTcWJ/hBO9oeQKlSxXKoiXTWQrdTR2GTpm19T0OfTEfPpSIT9CHm01pmAjGQia/REOANANBpFuVyGlBL5fB7RaNTpIe2aYRi4du1a66QXANi3bx+OHDmyqxlrcyY9EvJiNOSFeHS+X9FooNow0TAlhPh2H2bPo54dNcOArqlPXIOIrNEz4RyJRLCwsAAAHR3OpVIJV65cQblcBrA++z1x4gRGR0fbvvbjASuEQMij4VlrO27duoXl5WXUajW8613vgqb1zD8jItt09mf7HXi87typJ3Kvra3h0qVLrWDWdR1nz561JJh3QkqJWq0GoPe2xBPZpWfCORgMturMnXZTUEqJubk5fOtb30K9Xgew/vu5cOECYrGY7ePp5husRG7RM59HFUVBOBxGNptFpVJBrVaDx+Pe00KaTNPErVu3kEqlWo8NDAzg1KlTjpUTGM5Ee69nZs5A54VKrVbDm2+++UQw79+/H5OTk47WeQOBQOv1m1viichaDGeXKhQKuHTpUqs+rigKJiYmdr0iw0pCiNafZa1W6+ot8UROYTi70MrKCi5fvtwKPY/Hg3PnzrlqZ2On/FkSdaqeCmev19uqM+fzedd9HJdS4sGDB5ienkajsd73IhwO48KFC0+EoRswnIn2Vk+F8+Mfx+v1Okol+9pnbqXRaODGjRu4e/du67GhoSGcO3cOPp/PwZE9G8OZaG/1VDgD7gyVarWKN998E4uLi63HDh06hImJCaiq6uDINqfreqt/R3NLPBFZh+HssHw+j0uXLrXGoigKTp8+jYMHDzp+428rzT/L5pZ4IrJOz4Vzs/E+4Hw4Ly0t4fLly6hWqwDWa+Lnz5/H0NCQo+PaLre90RF1k57ZhNKkaRqCwSCKxSKKxSIajYbtpQMpJe7fv4/79++3HotEIpicnITX67V1LO1gOBPtnZ6bOQPOfhxvNBq4fv36E8E8MjKCs2fPdlQwA529JZ7I7Xo2nHVdf+KkECklzEf/7dUSu0qlgsuXL2Npaan12JEjR3Dy5EnX3vh7HkVRWm90lUqlVZ4hovb1XFkDAIaHRzA2NgYAMBomlktVVOtmq2G8KgTCHhUhj9bqbSzRXs/ibDaLq1evtrq5qaqKiYkJDAwMWPFbckwkEkEmkwGwPntuHiZLRO3pmXBuzoYbUmI2X8ZyqYZ0xUDJ2PyQU1UIRL0a+nw6EhE/+v0emFLuOKQXFhbw1ltvtZab+Xw+nDlzBsFgcPe/IZd4uu7McCayRteHc/Og0Xytjpl0CQ9zZdS3WbZoSIm1ioG1ioGZTAlRr4ZDsQAORAIQ2zhZWkqJu3fvYnZ2tvVYLBbD6dOnO6Ij3nbwpiDR3ujqcDalRMOUeGMxg7l8+815stU63lzM4fpKHi8MRbEv4t/0lOl6vY4bN25gZWWl9djo6CiOHz/e8ecXPs7r9cLn86FSqSCXy3XF+YxEbtCV4dwMzIViFW8sZFFtWLt7rdaQ+GYqg/l8BedGotCVJ2fR5XIZ09PTKBaLrceOHTuG8fFx128s2Y1IJIJKpQLTNFEsFp9YS05Eu9N1U5xmbfnyQgZ/OZ+2PJgflyxU8OV7S1grG63XzWQyuHTpUiuYNU3DCy+8gEQi0ZXBDLC0QbQXuiqcm6sqvp5M4362bMtr1hoSfzG3iqVSFaZp4t69ezAMAwDg9/tx4cKFJ5bsdSOGM5H1uiqcAeCbyQySBXvX2zYk8Pp8GqtlA5NTU/D5fOjr68OFCxdazYG6WTgcbn0qYDgTWaNrwllKiWsrecwXnDmVw5TA68k0aibwwgsv4MyZM9B13ZGx2K15PiMAlEql1icHItq9rghnU0pkKgZurRW3/uY9VDclLi9mEQgEem7FAksbRNbqmgS5uJB1eggAgOVSDXfTRdedsrLXGM5E1ur4cJZS4sZKAfla3emhtEwv51FtmD0V0AxnImt1fDibEribcbac8bSGlLiTdteY9prP52vteszlcj31xkS0Fzo6nE0pMZsrwzDdFwQPsmW4b1R7x83nMxJ1oo4OZ0UI182am6oNE3P5CswemkGytEFknY4O51zVQLbqnlrz02azpbbajHYahjORdTq2t4YpJVbL1q2n/ewnfw7f+M9/hFI+D38whHe+/3vwIz/9D6G30T0uXemt9b5uOp+RqNN17MxZAMhYGH7v/9DfwKf+8DX820u38E/+vy/j/s3r+Pef++dtXdMwJYqGe2f2VtM0DaFQCABQKBRQr/fO753Iap0bzkIgXalZdr3EkWPwPbbVWlEUpO7fa/u6a2WjZ+vOdp/PSNRNOjacASBn8drm3/vMp/HfnT+Gj7w8hfs3r+Gv/PBH2r5mzsU18b3AujORNTq25rx+IKu11/z+j34M3//Rj2Fu5ja++ge/hz4LjlyqSxO9c0uQ4UxklY6dOe/l0ubEkWM4eHICn/6ffrLta/VQRQMAEAgEoGnr7/ncjEK0ex0bzsoeT0cbhoHUg/ZrzooQPbsZpVaroVJxpksgUafr2HAWQkC1aA1xuVjEV77weRRzWUgp8eCtG/jd3/hVnH3lO9u+trbX7yIuxNIGUfs6tuYMAFGvhjULltMJIfDaf/h9/Otf/iTqRhWR+ADe8b4P4L/92E9bMsZe83Q4Dw8POzgaos7UsckhpUTMp1sSzr5AAL/4m79jwag2ivs9PbVLEODMmcgKHVvWkAD6fO4+acSjCvg11elh2E7X9dbxXPl8Hqa5d4fsEnWrjg1nRQgM+He/tdoO/T53j28vNWfPUkpuRiHahY4NZwAIejT0+907ez4Y9cOo13tyORlLG0Tt6ehwNqXE4VjQ6WE8k19TMRLyYebOHVy8eBGpVAqNRsPpYdmG4UzUno4OZ0UIjId98Kru+20cigVQbzSwtLSEQqGAmzdv4vXXX8fMzExPrP0NBoOtQ24ZzkQ7575U2yEB4FjcXbNnj6rgcCyAWrXaujEGAIZhYHZ2Fq+//jqmp6eRTqe7tuShKEpr9lypVFCtVh0eEVFnEbIL0kFKiT+dXXVN/+S3j8YwFva1ltBls1nMz89jaWlpQxgHg0EkEgkMDw9DVbtrZcfMzAxmZ2cBAJOTkxi0oFcJUa/oinA2pUTJaOA/3V/e054b2zEW8uEd433PfK5arSKZTCKZTKJWe7LdqaZpGB0dxfj4OPx+vx1D3XPLy8u4evUqAGD//v04cuSIwyMi6hxdEc7A+uz5TrqI6WXnlm35VAXvPTQIXREQz9l4YpomlpeXMTc398x6bH9/PxKJBPr6+p57HberVqv42te+BgCIxWI4d+6cwyMi6hwdu0PwaUIIHIuHUDIamMnYf/Kzrgi8ui8ObYtgBtbrscPDwxgeHkY+n8fc3BwWFxdbJY/V1VWsrq4iEAi0Sh7NTm+dxOv1wufzoVKpIJfLwTTN1k1CInq+rpk5P+7NxSzu2hjQHlXg1UQ/Il5t11u1a7Vaq+Tx9M0zVVVbJY/HbzB2gmvXrmFpaQkA8OKLLz5xziARba4rwxkAbq7kcWO1sOftOoO6ipfH4wh6VEt6aJimiZWVFczNzSGbzW54Ph6PI5FIIB6Pd0TJ4+HDh7hz5w4A4Pjx4xgfH3d4RESdoWvDWUqJTNXAxVQWeYuPs2o62hfE6YEwhMCeNDcqFAqtksfT/Sn8fj/Gx8cxOjrq6pJHNpvFzZs3EQ6HMTIygljfxpulAuiINxoiO3VtOANoHax6fSWPO+miZSs5QrqKC6Mx9NvU28MwDCSTSczPzz+z5DEyMoLx8XEEg+5a7w2s/x0037gKVQPpah2VegONR383qlhvDhX3exDQ1Q2/hqhXdXU4N0kpYZgS9zIl3M2UUK7vbhv1SNCLw30BDAe8kNib2fLzSClbJY9MJrPh+b6+PiQSCfT39zs6E5VSQggBo2HiXraEhUIV2aoBY4t3R10RiPl0jAZ9OBjztw5T4KyaelFPhHOTKSUEgMViFculGtIVA5mqgfomoRHUVfT5dMR8OvaF/fDrqmtmdYVCAfPz81hYWNhQ8vD5fK2Sh67b1xiqGcqZSg130iXM5cu7/rSiCoFExIejsSCiPr11baJe0VPh3NQM6eYPe8moo9ow0TDXzyZUFYGgrkJ7tOzr6e93E8MwkEqlMD8/v6Fnh6IorZJHKBTa03GYUqJhSry5lMPDXNnSax+M+nFmKAJFCFe8MRLZoSfDuRtJKbG6uoq5uTmk0+kNz8disVbJYy/WGi8UKri8kEWlsTeN9f2aggsjMQwFvXtyfSK3YTh3oWKx2Cp5PN2m1Ov1Ynx8HGNjY22XPJqlhitLOdxJF9u61nadiIdwepBrpan7MZy7WL1ex8LCAubm5lAuP1lqaO5STCQSuy55SClxeSGLBxaXMbZyOBbA2eGora9JZDeGcw+QUmJtbQ1zc3NYW1vb8Hw0GkUikcDAwMCOSh5vLGZxz4Gt8sB6m9ipwcjW30jUoRjOPaZUKmF+fv6ZJ7N4vV6MjY1hbGwMHs/ma7ilXF+W+OaSs030XxyJIhHx8yYhdSWGc4+q1+tYXFzE3NwcSqUnZ79CiFbJ4+leGFJKlOsmvnxvubWRxCm6IvC+Q4PwqIorV9IQtYPh3OOklEin05ifn8fKysqG5yORCBKJBAYHB1slj6/OrmKlXNvwvU4YCXrxciLu9DCILMdwppZyudwqedTrT/Yj8Xq9eNvb3475Yg2XFzY2ZHLS0yfPEHUDNtelFr/fj6NHj+Lll1/GiRMnnujVEYlEoGsa7qzZs2RuJ26niwxm6jqcOdOmpJTIZDKYn5/HeCKBuu7Ha3MbV3u4wXsODCDi1Vh7pq7BcKZt+3oyjfl8ZetvdMDBqB/nhqMMZ+oaLGvQtjRMiaRLgxkA5nLuHRvRbjCcaVtyVcOSU2X+8N/+Jn7mg+/HD04dxP/29/6mBVdcV5cSBWN3rWCJ3IjhTFsypcRaxbDkWvGhEXzw73wc7/2BD1lyvcetlWutAxaIOp17zzci1xAAMhaF8zve9wEAwP0b17C6mLLkmk3pioH9Eb+l1yRyCmfOtCUhxJ6dw2ilQq3OG4LUNRjOtC1Ob9XejnoHjJFouxjOtC1WHY67l5jN1E0YzrQtagdUC7hLkLoJbwjStuiqNe/jjXodjUYdjUYD0jRRq1YghAL9OS1Kt8vTCe8gRNvEcKYtSSkR9epYLrXfie53f/1X8P/82v/R+vqHXjiM0297J37p33yh7WvHvLprTkcnahe3b9OWTCkxn6/gm6mM00N5rneO92Ek6OWKDeoKrDnTlhQhEPe1dxisHeI+ncFMXYPhTNsS9GjwWVR33gtBXYVXU50eBpFl3PvTRq4ipcTBWMDpYWzqUCzArdvUVRjOtG2HYwG4sWigCOBQNMAbgdRVGM60LUII+DQVoyGv00PZIBH2W7bUj8gt+C+ats2UEqcGwq6aPSsCONkfYkmDug7DmbZNEQIRj4YT/SGnh9IyMRBGUFdZ0qCuw3CmHRFC4GR/CBGv8/uX+nw6jvUFuXyOuhLDmXblbaMxqA6GoqYIvG00ZsnpLERuxHCmHVOEQNij4Z3jfVAcyGdVAK8k4giwnEFdjOFMu6IIgcGAB+8Y77O1Y50mBF5OxBH36Qxm6mrsrUFtkY/OF/xGMo1y3dzT1wrqKt4+GkNYV1CtVhEMBvf09YicxHCmtplSwpQSV5ZyuJ8t78lrHI4FMDkYhlGr4er0NGq1Gi5cuACfz7cnr0fkNIYzWUJKCSEElopVvLmURaHWsOS6EY+Gs8NRDAQ8ME0TV65cQTqdBgCEw2GcO3cOqsqeGtR9GM5kqWY/5aViFXczRaQK1R2vqBAAxsI+HIkF10P5sR7NtVoNly5dQqVSAQAMDQ1hYmKCy+mo6zCcaU80A7VSb2ChWEWmYiBdMZCtGhvOI1QFEPXqiPl09Pl0jAS98Grqpo3zC4UCLl++jEZjfXZ+6NAhHDx40IbfFZF9GM6050wpIbC+gUVKCcOUrdO8VSGgK6L1nMT2zgJcWVnB9PR06+vTp09jaGhoj34HRPZjOFPHevDgAe7evQsAUBQF58+fRzgcdnhURNbgOmfqWPv378fw8DAAwDRNTE9Po1qtOjwqImswnKljCSFw4sQJRCIRAEC1WsXVq1dbtWiiTsZwpo6mqiomJyfh9a73mc7lcrh16xZYraNOx3Cmjuf1ejE1NQVFWf/nvLCwgIcPHzo8KqL2MJypK4TDYZw6dar19czMDFZWVhwcEVF7GM7UNYaGhp5Y73z9+nUUCgXnBkTUBoYzdZWDBw9icHAQANBoNDD9qA8HUadhOFNXEULg1KlTCIXWj9KqVCq4du0aTHNvO+YRWY3hTF1HVVVMTU3B4/EAADKZDG7fvs0VHNRRGM7UlXw+HyYnJ1srOJLJJObn5x0eFdH2MZypa0WjUZw4caL19Z07d7C2tubgiIi2j+FMXW1kZAT79+8HsN5z+tq1ayiVSg6PimhrDGfqeocPH0Z/fz8AoF6v48qVKzAMw+FRET0fw5m6nhACExMTrTMHy+UyV3CQ6zGcqSdomoapqSnoug4ASKfTmJmZcXhURJtjOFPP8Pv9mJycbB1pNTc3h2Qy6fCoiJ6N4Uw9JRaL4fjx462vb9261TowlshNGM7Uc8bGxpBIJAB8ewVHuVx2eFRET2I4U086cuQI4vE4AMAwDExPT6Nerzs8KqJvYzhTT1IUBRMTEwgEAgCAYrGI69evc4s3uQbDmXqWruuYmpqCpmkAgNXV1daBsUROYzhTTwsEAjh9+nRrBcfs7CwWFhYcHhURw5kI8XgcR48ebX198+ZNZLNZB0dExHAmAgCMj49jbGwMwPoKjqtXr6JSqTg8KuplDGcirG/xPnbsGGKxGACgVqthenoajUbD2YFRz2I4Ez2iKAomJyfh8/kAAIVCATdu3OAKDnIEw5noMbqu48yZM1BVFQCwvLyM+/fvOzso6kkMZ6KnBINBTExMtL6+f/8+lpaWHBwR9SKGM9EzDAwM4MiRI62vb9y4gXw+7+CIqNcwnIk2sW/fPoyMjAAATNPE9PQ0qtWqw6OiXsFwJtqEEAInTpxAJBIBAFSrVa7gINswnImeQ1EUTE1Nwev1AgDy+TzeeuutXa/gkFI+8R/RZoTkvxCiLeXzeVy+fLl1tNXhw4dx4MCB5/4aU0oIrM/ATSmRr9ZRNBowH/3IKUIgoKuIeDUoQqwH9qPHiRjORNu0vLyMq1evtr6enJzE4ODghu9rhvJisYpUoYpM1UC2asDc5CdNAIh6NcR8OkZDPowEvQxpYjgT7cT9+/dx7949AICqqjh//jxCoRCA9ZKFYUrcy5RwL1tCydhdbdqvKTgUDeBQLAiPKlpNmai3MJyJdkBKievXr7fWPff19WHqzBkoQuDWWhE3VvObzpB3ShHAiXgIJ/tDnEn3IIYz0Q41Gg288cYbCAQCOHnyJIpGAxcXskhXjD15vZhXw4ujMYQ9GmfRPYThTLQLhmFA13U8yJbwxmLWstnyZgSAF4YiONwX3NsXItdgOBPt0p21Iq4s52x9zYmBME72h2x9TXIG1zkT7ZCUEncz9gczAFxfyePWWsH21yX7MZyJdsCUEsulGt5ctD+Ym64u55EqVFrrpak7MZyJtklKCVNKXFrIOD0UXF7IomFyl2E3YzgTbZMQAleWcijXTaeHgmrDxBuLWa7e6GIMZ6JtWC9nVHE/W3Z6KC1z+QrLG12M4Uy0DYoQeGvVfTfi3lorcHNKl2I4E21BSolirY6lUs3poWywVjaQqxqsPXchhjPRNsxkSk4PYVMzafeOjXaP4Uy0BSEEZnPuDcDZXBmcN3cfhjPRFopGHbWGNfFXNwz8y1/6BD780gQ+/NIEPvvJn0OjXm/rmg0pUai1dw1yH4Yz0XOYUmKtbF1Do9/99V/BzcvfwK/8wZ/gV/7gT3Dj0tfxhX/xqbavu1Y2uGqjyzCciZ5DAMhY2G3uK7/3efz1H/9J9A0No29oGB/88Y/jP3/ht9u+brpqgGs2ugvDmeg5hBDIWVQyKGQzWF1I4eCp063HDp48jZXkPIr59raD56oGN6R0GYYz0RbqpjU7AiulIgAg+Og07/X/j64/V2xvDXV9r3uWku0YzkRbsCr3fIH1XsylfL71WOnRjNkXbK8NKLO5+zCcibagWFQtCEVj6B8Zxb0b11qP3b9xDQOjYwiGI8/5lVtTWdHoOgxnoi3oinU/Jt/1/T+IL/yLX0V6eQnp5SV84TOfwnv++ofavq5m4RjJHTSnB0DkZqaUiHg1LBSrllzvB/7OT6GQSePjf/U7AADv+p7vwwd/7Cfavm7Eq0FKyZuCXYTHVBE9hyklkoUKvpHMOD2U57owEsW+iJ9NkLoIPwsRPYciBOI+j9PD2FLcpzOYuwzDmWgLAV2FT3Xvj4quCIQ8rFB2G/f+iyNyCSklDkT9Tg9jU/sjfkgJ3Lt3D8Vi0enhkEVYcybagpQSlYaJL80sOT2UZ/rugwMoZdZw/fp1AEA0GsXY2BgGBwehqqrDo6Pd4mchoi0IIeDXVIwGvUhZtGrDKoMBD8JeHXeSydZj2WwW2WwWt2/fxvDwMMbGxhAKtbfJhezHmTPRNphSIlMx8Kezq04P5Qnv2hdHv9+DumFgcXERyWQSpdLG3tPhcBhjY2MYGhqCpnFO1gkYzkTbJKXE9HIed9LuqOsejPpxfiT2xGNSSmSzWaRSKSwtLcF8qi+IqqoYHh7G6OgowuEw10W7GMOZaAcapsR/ur+MotFwdBx+TcV3HxqAKsSmAWsYBpaWlpBMJlEobGysFAqFMDY2huHhYc6mXYjhTLQDzfLGn82uOno01KuJOAYCnm2tbZZSIp/PI5lMYmlpCY3Gk28siqJgaGgIo6OjiEajnE27BMOZaIeklJjLV/DNVMaR1z8/HMWBqH9XIVqv11uz6fxj3fGaAoEAxsbGMDIyAl3XrRiu7Zonwgis38yVUrbeSDtpow7DmWgXpJSYzZVxeSFr6wz67HAEh2NBS65VKBSQTCaxuLiI+lPnGAohMDg4iLGxMcRiMVfPpk0poTwK4XytjnTFQLZaR8OUrec0RSDi1dDv9yCoqxBCtJ5zK4Yz0S5JKZEqVnExldnzZveqEDg/EkUi7LM8KBuNBpaXl5FMJpHNZjc87/f7MTo6itHRUXg87tjK3owtUwIPc2U8yJWRqdSwnXN4VSEQ9+s4EA2s/3k+etxtb0AMZ6I2mFKi1jBxKZXFYmlv1kAP+D14cTQGv6bseYAUi0WkUiksLCzAMJ48O1EIgYGBAYyOjiIejzsWZlJKlOsm7qSLeJAtwWjjjdGjKjgY9eNoXxAeVXHVTJrhTNSmZqvO+5kSppdzbYXF4zRF4PRAGEf6gra3AzVNE8vLy0ilUkin0xue9/l8GB0dxcjICHw+nz1jkhICwEy6hGsruW3NkrdLUwSmBiM4FAu4ptzBcCayiCklpARmc2XczRSRre7uYNiIR8PhWAD7owGowvmP2+VyGclkEgsLC6jVahue7+/vx9jYGOLxOJQ9avpvSolyvYGLqQxWy9adhv60oYAHF0Zj8LpgFs1wJrJYc+a1Vq4hVagiUzGQrhqoNZ59UKxHEYj5dMR8OkZDPvT7Pa6ZvT3ONE2srq4imUxibW1tw/Mej6dVm/b7rWsUJaXESqmG1+fTqNsQV7oi8GoijqjDbVgZzkR7pLmEq/kDXqk3UDIaaDwqe6iKgE9TENDXN4A0TBNCCNeF8rNUKhWkUimkUilUqxtr7X19fRgbG8PAwEBbs2kpJRaLVfxlMm3rIbaqEHglEUfc71xAM5yJHFSr1XD79m3k83lEIhFMTEw4PaQdkVJibW0NyWQSq6ureDpOdF3HyMgIxsbGEAgEdnRtU0qslQ38+dyqI6eLa4rAu/f1I+LVHAlohjORg0zTxFe/+lVIKREIBPDSSy85PaRdq1arrdl0pVLZ8HwsFsPo6Oi2WplKKVEzJb58bwk1K+/87ZBfU/Ddhwafu01+rzCciRz2zW9+s9X74t3vfnfH92CWUiKdTiOVSmF5eXnDbFrTtNZsOhjcfEPNX86nkSxsDHm7HYj6ceGpBlN2YDgTOezGjRtYWFgAAJw/fx7RaNThEVmnVqthYWEBqVTqma1MI5FIq5Vp803JlBLJfAXfcGh7/LO8kujDYMBra3mD4UzksLm5Ody+fRsAcPz4cYyPjzs8Ius1W5kmk0ksLy9v2sr04MGD0HQPvnR3adPVLU7wayref3jQ1tIG+wQSOezxU0qe1dqzGwghEIvFEIvFYDx2MEDzzMNGo4FUKoUDBw9iNldyVTADQLneQLJQwWjIZ9vsmeFM5LDHw/lZneK6ja7rSCQSGB8fRy6XQyqVwuLiIuLxOHxeL+6lck4P8ZnuZkoYD9t30C/DmchhmqbB7/ejXC6jWCzCNM0922nnJkIIRKNRRKNRHD16FEa9jrVyDZld7qzca8ulGgq1equr3V7r/n8BRB0gHA4DWF9aVy6XHR6N/TRNg8/rxVze+dUZzzOXK9vWIpbhTOQCvVbaeBYhBNIV6/pmfPMrf4x/8Nfeiw+dO4K//a5z+OPP/19tXzNdNVhzJuolvXBTcCtSSmQtCuc3XvsTfOYffQIf/+VP49SLL6FcyCOzutz2dTMWvnlsheFM5ALNsgbQuzPnotGwrLHRb//qL+MH/u5PYfKllwEAoWgMoWis7euW6yZqDRMede+LDixrELmAx+NpnTJSKBQ27KrrBYWaNTcCK6US7l67gnIhj4/9lXfhb736Av7pT/0Y0stLllzfqnFuheFM5BLN0ka9Xn9mp7duJqW0bNZczGUgpcSfffEL+PnP/jb+2R9/DZqm41P/48csuX7DpjdOhjORS/R8acOizPMF1vt1fOBHPoKh8QT8wSB+8GM/jenX/xyVZ2wh3ym7PtQwnIlcotdvClq1CiIYiWJgbPyZa5GtKBepij2rNRjORC7RyzNnIdYPHrDKd/83P4w//Defw+piCtVKGf/vr/2fmHrnq/A/pwvednltuBkIcLUGkWv4fD6oqopGo9GTM+eoV7fsWt/3o38fhUwG/+C/fi8AYPKlV/AT//jTbV9XFQJB3Z6WruxKR+Qily9fRjabBQC88sorrRUcveLL95aRt2k1xG70+3V8x/4BW16LZQ0iF3m8tNGLs+c+n3Wz570Q8+q2LXNkOBO5SC/fFDSlxGDA3Z8UhoJe9tYg6kW9fFNQEQKJsB8em1ZD7JRfUzAStO80FIYzkYsEAoHWErBemzkDgCKA/dGdndJtl0OxgG2zZoDhTOQqiqK0Dj0tlUpoNBoOj8h+R/rcF84CwKFY0NYzBBnORC7TyzcFhRAI6hoOuWz2fCwetL3cwnAmcplevikIrO/imxqKwK/Zs554K2GPhomBsK2HuwIMZyLX6eWbgsD67FkRwIWRqNNDgQDw4qgz42A4E7lM8LEtxr04czYMA/fu3sVQ0Iujfe1vt27Hqf4QYl7d1lpzE7dvE7mMpmkIBAIolUo9deArsH4T9MqVKyiXy9A0DWcOHECtYWI2Z/+5ikdiAZwcCG/9jXukN/7GiTpMs+5smiZKFrS57ARra2u4dOlS64Dbhw8folqt4sJIFAeiflvHcrQviBeGnS2rMJyJXKiXbgpKKTE3N4crV66gXl/vqxEMBnHhwgV4vV4AwIWRGE4PhLHXCyZUAbwwFMGZocjevtA2sKxB5EJP3xQcGRlxcDR7xzRN3Lp1C6lUqvXYwMAATp06BU1bj6fmKonj8SBGQ15cTGWQqVrfHKnfr+PFkRgCNnWd2wrDmciFemHmXKvVcPXq1VYXPgDYv38/Dh8+/Mxla0IIhDwavuvAAG6tFXEnXUS1YbY9Dr+m4Fg8hCOPdgDavWRuMwxnIhfyeDzwer2oVqutA1/dEhpWKBQKmJ6eRqVSAbC+M/LEiRNbfkJQHptFH4sHMZ+v4G6miNWyseMxDAY8OBwLYCzkA7Aeym76E2Y4E7lUKBRCtVpFvV5HpVKB32/vTbG9srKyguvXr7e2pns8HkxOTiIa3f4NuGaQjod92Bfxo2TUsVI2kKms/5erGjBMCYn1fh2aIhD16oh5dcR8Ogb8Hvh1FaaL3/QYzkQuFQqFsLq6CmB9ptnp4SylxMOHDzEzM9N6LBQKYWpqCj6fb1fXbM6kA7qGhKZiX9j33LCVshnY4olf70YMZyKXevqm4ODgoIOjaU+j0cCtW7ewsLDQemxoaAgnT56EqlpzA247Qeu20sXzMJyJXKpbbgpWq1VcvXoVuVyu9dihQ4dw4MAB15YU3IDhTORSPp8PmqahXq93bI+NfD6P6elpVKtVAOs3/k6dOoWhoSGHR+Z+DGcilxJCIBQKIZPJoFaroVarddSBr0tLS7hx4wZMc325m9frxdTU1BPlGtocdwgSudjjpY1OmT1LKXHv3j1cu3atFcyRSAQXLlxgMO8AZ85ELvZ04/3+/n4HR7O1RqOBmzdvYmlpqfXY8PAwTpw4YdmNv17BcCZysU66KVipVHD16tUnZvhHjhzBvn37eONvFxjORC4WCASgKApM03R1WSObzeLq1auo1WoAAFVVMTExgYGBAYdH1rkYzkQu1jzwNZ/Po1wuo16vtxoCucXCwgLeeuutVn3Z5/NhamrqiVk/7RxvCBK5nFtLG1JKzMzMPLEiIxqN4sKFCwxmCzCciVzOjadx1+t1XL16FbOzs63HRkdHcfbs2Y5a7udm7vp8REQbuG3mXC6XMT09jWKx2Hrs2LFjGB8f540/CzGciVzOTWudM5kMrl69CsNYb9GpaRpOnz6NeDzu6Li6EcOZyOVUVXXFga/JZBK3bt2ClBIA4Pf7cebMGQQCAdvH0gsYzkQdIBQKoVQqQUqJUqlk6w030zQxMzODubm51mN9fX04ffo0dF23bRy9hjcEiTqAUzcF6/U6pqennwjmRCKBM2fOMJj3mJDNzyhE5FqlUgn5fB6hcBjBTcoIppQQsO4MvFKphOnpaZRKJeDRdY8fP46xsTFLrk/Px3AmcjFTSihCoGFKZCo1ZKp1pCsGCrU6GlJCSkBVBDyKgqhPQ59PR9z37SOYdnvSx9raGq5du4Z6ff2Ua13Xcfr0afT19Vn526PnYDgTuVAzWJeKVdzNFJEqVLGTH9SApuJQLIBDsQA8qrKjoJ6bm8OdO3daN/6CwSCmpqY6/pisTsNwJnKRZmniXqaEO+kiCkajrespAhgL+TAxEEZQV59b8jBNE7dv30YymWw91t/fj4mJCddtGe8FDGcil5BSomg0cDGVwVrFsPTaigAmBsI41hd84oDTJsMwcPXqVWQymdZj+/fvx+HDh7mxxCEMZyKHSSkhhMCttQKur+Rh7uFPZNyn48XRGAK62groYrGI6elplMtlAOs3/k6ePImRkZG9GwhtieFM5KDmj9/FhSwe5sq2vKauCLySiCPm05HP5fCtb30LjcZ6+cTj8WBychLRaNSWsdDmuM6ZyCHNYP56MmNbMAOAYUq89nAN6XINgUAAPp8PwPpGlwsXLjCYXYIzZyIHXUpl8MDGYH6crgi8e18cWqOO+/fv4eTJkzxKykUYzkQOMKXEXK6MiwtZR8cR9mh4z4EBCGHd5hWyBssaRDaTUsJomPjWUs7poSBfq+P6qnuPv+plDGcimwkhcGkhC2Mvl2XswO21IjJVAyY/RLsKw5nIRqaUWCpWsVCsOj2UFgngzcXcrrd6095gOBPZSBECM+ni1t9os3TFQKZigLeg3IPhTGQTKSXKRgMpF82aHzeTcd+bRi9jOBPZ6G6m5PQQNjWXK6PBmbNrsJsJkU2EEFgoVtq+zqd/9ifx5//h96E91uz+Fz73eZw492Jb121IYKlYw0jIy/qzCzCciWxiSolctW7Jtf7LH/owPvKJX7LkWo9LVwyMhLyWX5d2jmUNIptkq8aOejI7IVM1OGt2CYYzkQ1MKZEuW9cG9M/+/e/iwy9N4OPf85344m/+BkzTtOS6GYtbldLusaxBZJNy3ZoA/as/8hH89z/z8whFY5iZfhP/9Kd+DEJR8L1/46NtX7vaMNs63oqsw5kzkU2sWglx+PQZROP9UFUVx89ewPf96N/HX3zpi5ZcGwB3CroEw5mowwmFP8bdiH+rRDZRLSoV/MWXvohSIQ8pJe5Mfwu//5l/hne87wOWXBvYeIQVOYM1ZyKb+HVr5kJf+r9/C7/xCz8Ds1FHfGgE7//Qh/Ff/c0ft+TaXlVhOLsE+zkT2SRTMfCVBytOD+O5RoJevJyIOz0MAssaRLaJeDW4fU4a8+m8IegSDGcimyhCIOp1dyWxz6u7/g2kVzCciWwipcRIyOf0MDalCoHBoIfHVbkEw5nIJkIIHI4FXDsz3RfxWbaihNrHcCaykU9TMerSxkJH+4JOD4Eew3AmspEpJY7E3BeC/X4dEa/OkoaLMJyJbKQIgcGgF2Muqj0LAGeHolyl4TIMZyKbSSlxbiQKj+qOWerxeAgRr8bNJy7DcCaymRACuiJwdijq9FAQ8Wo4NRBiOcOFGM5EDlCEQCLix6FYwLExeBSBl0b7HHt9ej6GM5GDzg5FsC9sf/1ZUwRe2RdH0KOynOFS7K1B5KDmj98bi1ncz5ZteU2PquDVRJx1ZpdjOBM5TEoJIQRm0kVcXc5b1pT/WQb8Hrw4GoNPY/c5t2M4E7mElBLluomLqQxWyjVLr60KgcnBMI70BVtvBuRuDGciF2kG54NsCXfSRWSr9baupwogEfHjVH8Yfk1hKHcQhjORCzUPWV0t1zCTLiJZqMDcwU9qyKPiUDSAg9EANGU9kBnMnYXhTORizZA2pUS+WsdaxUCmYqBg1NEwJSQARazf5It5dfT5dPT5PfCqCk/R7nAMZ6IOYkoJgWfPgp/3HHUehjMRkQtxEwoRkQsxnImIXIjhTETkQgxnIiIXYjgTEbkQw5mIyIUYzkRELsRwJiJyIYYzEZELMZyJiFyI4UxE5EIMZyIiF2I4ExG5EMOZiMiFGM5ERC7EcCYiciGGMxGRCzGciYhciOFMRORCDGciIhdiOBMRuRDDmYjIhRjOREQuxHAmInIhhjMRkQsxnImIXOj/ByOKyUZ6LdjcAAAAAElFTkSuQmCC"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": "",
   "id": "2793ca5f1f61d6f2"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
